package alo.p6.work4;

import alo.p6.BinarySearchTreeNode;
import java.util.Stack;
/**
 * @ClassName BSTToDLL
 * @Description 二叉搜索树转换为双向循环链表
 * @Author Fanxc
 * @DATE 2021/2/21 16:18
 * @Version 1.0
 */
public class BSTToDLL {
    //使用递归
    private BinarySearchTreeNode leftLast = null;//左链表的最后一个
    public BinarySearchTreeNode Convert(BinarySearchTreeNode root) {
        if (root == null)
            return null;
        if (root.getLeft() == null && root.getRight() == null) {
            leftLast = root;// 最后的一个节点可能为最右侧的叶节点
            return root;
        }
        // 1.将左子树构造成双链表，并返回链表头节点
        BinarySearchTreeNode left = Convert(root.getLeft());
        // 2.如果左子树链表不为空的话，将当前root追加到左子树链表
        if (left != null) {
            leftLast.setRight(root);
            root.setLeft(leftLast);
        }
        leftLast = root;// root追加左子树后，左子树的最后一个为root，当根节点只含左子树时，则该根节点为最后一个节点
        // 3.将右子树构造成双链表，并返回链表头节点
        BinarySearchTreeNode right = Convert(root.getRight());
        // 4.如果右子树链表不为空的话，将该链表追加到root节点之后
        if (right != null) {
            right.setLeft(root);
            root.setRight(right);
        }
        return left != null ? left : root;//如果左链表不为空，返回left，否则返回root（即链表的头结点）
    }

    class Solution {
        public BinarySearchTreeNode Convert(BinarySearchTreeNode root) {
            if(root == null) return null;
            BinarySearchTreeNode p = root;//当前结点
            BinarySearchTreeNode pre = null;//前结点
            //使用栈结构
            Stack<BinarySearchTreeNode> st = new Stack<BinarySearchTreeNode>();
            boolean isFirst = true;
            //非递归的LDR中序遍历
            while(p!=null||!st.isEmpty()){
                while(p!=null){
                    st.push(p);
                    p = p.getLeft();
                }
                p = st.pop();
                if(isFirst){
                    root = p;
                    pre = p;
                    isFirst = false;
                }else{
                    p.setLeft(pre);
                    pre.setRight(p);
                    pre = p;
                }
                p= p.getRight();
            }
            return root;
        }
    }

}
